
// 93.复原IP地址
class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        int n = s.size();
        // 使用DFS来完成
        
        vector<string> ret;
        string tmp;
        function<void (int pos , int point)> dfs = [&](int pos , int point)
        {
            if(point == 3)   // 判断最后是不是有效整数
            {
                string last = s.substr(pos);
                if(pos == n || last.size() > 3 || stoi(last) > 255) return ;
                if(last.size() == 1 || last[0] != '0') ret.push_back(tmp + last);         // 判断有没有前导零
            }
            for(int k = 1; k <= 3 && pos + k < n;k++)              // 取字符串,长度最大为3
            {
                string str = s.substr(pos , k);
                if(str.size() == 0 || stoi(str) > 255 || (k > 1 && str[0] == '0')) break;
                int len = tmp.size();
                tmp += str + "." ;
                dfs(pos + k , point + 1);
                tmp.erase(len);
            }
        };
        dfs(0 , 0);
        return ret;
    }
};